package com.Algorithm.prim;

import com.atguigu.graph.Graph;

import java.util.Arrays;

/**
 * @author shkstart
 * @create 2021-08-31 1:10
 */
public class PrimAlgorithm {
    public static void main(String[] args) {
        char[] data = new char[]{'A','B','C','D','E','F','G'};
        int verxs=data.length;
        //邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通
        int [][]weight=new int[][]{
                {10000,5,7,10000,10000,10000,2},
                {5,10000,10000,9,10000,10000,3},
                {7,10000,10000,10000,8,10000,10000},
                {10000,9,10000,10000,10000,4,10000},
                {10000,10000,8,10000,10000,5,4},
                {10000,10000,10000,4,5,10000,6},
                {2,3,10000,10000,4,6,10000},};
         //创建图
        MGrch graph = new MGrch(verxs);
        //创建最小生成树
        MinTree minTree = new MinTree();
        //用树生成图
        minTree.createGraph(graph, verxs, data, weight);
        //用最小生成树显示矩阵
        minTree.showGraph(graph);
    }
}
//创建最小生成树
class MinTree{
    //一一赋值
    //创建对应的图
    public void createGraph(MGrch graph,int verxs,char data[],int[][] weight){
         int i,j;
         for (i=0;i<verxs;i++){
             graph.data[i]=data[i];
             for (j=0;j<verxs;j++){
                 graph.weight[i][j]=weight[i][j];
             }
         }
    }
    //显示图的邻接矩阵
    public void showGraph(MGrch graph){
        for (int[] link:graph.weight){
            System.out.println(Arrays.toString(link));
        }
    }
}
//创建图
class MGrch{
    int verxs;//表示图的节点个数
    char[] data;//表示节点的数据
    int[][] weight;//存放边，我们的邻接矩阵
    //初始化
    public MGrch(int verxs){
        this.verxs=verxs;
        data=new char[verxs];
        weight=new int[verxs][verxs];
    }


}